package dynamicPlan;

/**
 * @author tongchen
 * @create 2023-08-04 16:53
 */
public class OneBag {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int i = maxValue(weight, value, 4);
        int i1 = maxValueForOne(weight, value, 4);
        System.out.println(i);
        System.out.println(i1);
    }
    public static int maxValue(int[]weights,int[]val,int cap){
        //创建dp数组
        //i为物品,j为容量
        int[][]dp=new int[weights.length][cap+1];
        //初始化
        for(int i=weights[0];i<dp[0].length;++i){
            dp[0][i]=val[0];
        }
        //遍历
        for(int i=1;i< weights.length;++i){
            for(int j=1;j<cap+1;++j){
                //先变化，避免后续因为大小问题无法变化
                dp[i][j]=dp[i-1][j];
                if(weights[i]<=j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weights[i]] + val[i]);
                }
            }
        }
        //返回最终结果
        for (int i = 0; i < weights.length; i++) {
            for (int j = 0; j <= cap; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
        return dp[weights.length-1][cap];
    }
    public static int maxValueForOne(int[]weights,int[]val,int cap){
        //创建dp数组
        int[]dp=new int[cap+1];
        //遍历顺序（先物品后容量，容量从后往前遍历）
        for(int i=0;i< weights.length;++i){
            for(int j=cap;j>=weights[i];j--){
                    dp[j]=Math.max(dp[j],dp[j-weights[i]]+val[i]);
            }
        }
        return dp[cap];
    }
}

